using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0020. 有效的括号")]
    public class No0020_IsValid : AbsBaseTestItem
    {
        /*
        给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
        有效字符串需满足：
            左括号必须用相同类型的右括号闭合。
            左括号必须以正确的顺序闭合。
        注意空字符串可被认为是有效字符串。
        */

        public override void OnTest()
        {
            Assert.TestExe(IsValid, "]", false);
            Assert.TestExe(IsValid, "()", true);
            Assert.TestExe(IsValid, "()[]{}", true);
            Assert.TestExe(IsValid, "(]", false);
            Assert.TestExe(IsValid, "([)]", false);
            Assert.TestExe(IsValid, "{[]}", true);
        }

        public bool IsValid(string s)
        {
            var inDic = new Dictionary<char, char>() {
                { '(', ')' },
                { '[', ']' },
                { '{', '}' },
            };
            var outDic = new Dictionary<char, char>() {
                { ')', '(' },
                { ']', '[' },
                { '}', '{' },
            };
            var stack = new Stack<char>();
            for (int i = 0; i < s.Length; i++)
            {
                char c = s[i];
                if (inDic.ContainsKey(c))
                {
                    stack.Push(c);
                    continue;
                }
                if (stack.Count <= 0)
                {
                    return false;
                }
                char nc = stack.Pop();
                if (nc != outDic[c])
                {
                    return false;
                }
            }
            return stack.Count == 0;
        }
    }
}
